Reed-Muller expansion

In logic synthesis Reed-Muller (or Davio) expansion is a decomposition of a boolean function.

For a boolean function f(x_1,...,x_n) we set with respect to x_i:

\begin{align} f_{{x_i}}(x) & = f(x_1,...,x_{i-1},1,x_{i%2B1},...,x_n) \\[3pt] f_{\overline{x_i}}(x)& = f(x_1,...,x_{i-1},0,x_{i%2B1},...,x_n) \\[3pt] \frac{\partial f}{\partial x_i} & = f_{x_i}(x) \oplus f_{\overline{x_i}}(x)\, \\ \end{align}

as the positive and negative cofactors of f, and the boolean derivation of f.

Then we have for the Reed-Muller or positive Davio expansion:

f = f_{\overline{x_i}} \oplus x_i \frac{\partial f}{\partial x_i}.

Similar to binary decision diagrams (BDDs), where nodes represent Shannon expansion with respect to the according variable, we can define a decision diagram based on the Reed-Muller expansion. These decision diagrams are called functional BDDs (FBDDs).

References